package org.usmile.algorithms.learn.graph.bfs;

import org.usmile.algorithms.learn.graph.AdjList;
import org.usmile.algorithms.learn.graph.Graph;

import java.util.*;

public class ConnectedComponent {
    @SuppressWarnings("unchecked")
    public List<Integer>[] bfs(Graph graph) {
        if (graph == null) {
            return new ArrayList[0];
        }

        Queue<Integer> queue = new LinkedList<>();
        int ccCount = 0;
        int[] visited = new int[graph.getV()];
        Arrays.fill(visited, -1);
        for (int v = 0; v < graph.getV(); v++) {
            if (visited[v] == -1) {
                ccCount++;
                queue.offer(v);
                visited[v] = ccCount;
                while (!queue.isEmpty()) {
                    int curr = queue.poll();
                    for (int w : graph.adj(curr)) {
                        if (visited[w] == -1) {
                            queue.add(w);
                            visited[w] = ccCount;
                        }
                    }
                }
            }
        }

        List<Integer>[] result = new ArrayList[ccCount];
        for (int v = 0; v < graph.getV(); v++) {
            int ccId = visited[v] - 1;
            if (result[ccId] == null) {
                result[ccId] = new ArrayList<>();
            }

            result[ccId].add(v);
        }

        return result;
    }

    public static void main(String[] args) {
        Graph graph = new AdjList(8);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(1, 4);
        graph.addEdge(3, 2);
        graph.addEdge(5, 6);

        System.out.println(Arrays.toString(new ConnectedComponent().bfs(graph)));
    }
}
